package com.xcoder.leetcode;

/**
 * https://leetcode-cn.com/problems/coin-change/
 */
public class _322_零钱兑换 {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 2;
        coinChange(coins, amount);
    }

    private static int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    private static int coinChange(int[] coins, int remain, int[] count) {
        if (remain < 0) {
            return -1;
        }
        if (remain == 0) {
            return 0;
        }
        if (count[remain - 1] != 0) {
            return count[remain - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int c : coins) {
            int res = coinChange(coins, remain - c, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[remain - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[remain - 1];
    }
}
